The present invention generally relates to managing the transmission of data packets in a packet-switched network. The invention relates more specifically to managing the dropping of packets in a packet stream of an integrated network that carries data, voice, video, and other traffic.
Demand for voice and video digital services is increasing. To meet this increasing demand in an efficient and cost-effective manner, voice and video data may be transmitted over a packet-switched network that handles other types of network transmissions, in addition to the voice and video transmissions.
Such networks are required to handle, simultaneously, different kinds of network transmissions (xe2x80x9ctrafficxe2x80x9d) that may have different requirements. A key requirement is providing adequate quality of service (xe2x80x9cQoSxe2x80x9d) for each type of traffic.
Transmission of voice and video data are examples of real-time transmission. Real-time transmissions require relatively little delay, and are characterized by high but relatively predictable bandwidth utilization. Data traffic, in contrast, is more tolerant to delay, but tends to arrive in unpredictable bursts of high bandwidth. In a network element that handles both types of traffic, such as a router or switch, to provide adequate QoS, it is important to guarantee small, consistent delays for real-time transmissions without starving the data traffic.
A conventional method of handling real-time transmission is the xe2x80x9creservationxe2x80x9d method. Under the reservation method, bandwidth requirements for a transmission are reserved for the entire duration of the transmission along the entire transmission path, from the transmitter to the receiver. Unallocated portion of bandwidth is used for non-real-time transmissions. A drawback to the allocation method is that the network elements that participate in the real-time transmission must be coordinated. This coordination entails handshaking between the participating network elements, resulting in overhead and delay in initiating the transmission.
An approach which eliminates the need to allocate is the differentiation approach (Diff Serv). Under the differentiation approach, each network element in a network may handle different types of network transmissions differently, processing each type according to its needs. However, a drawback of the DiffServ approach is that it only solves the problem of bandwidth contentions among different traffic types or classes, and overlooks contentions among traffic streams of the same classes and/or among packets of the same stream. As a result, DiffServ approaches tend to implement a sub-optimal drop policy for real-time traffic.
In this context, xe2x80x9cdropxe2x80x9d means that a packet is not processed by the network element, and not transmitted along the remainder of the transmission path. Some types of real-time traffic tolerate dropped packets relatively well. For example, the quality of a voice data transmission does not significantly deteriorate when only a few packets are intermittently lost. However, when sets of adjacent packets (xe2x80x9cgapsxe2x80x9d) are dropped, the quality of a voice transmission diminishes significantly. Under heavy traffic conditions, the size and number of gaps are more likely to increase, significantly diminishing the quality of a voice transmission.
U.S. Pat. No. 4,979,165 (Dighe et al.) describes a multiple queue bandwidth packet reservation system for networks that use fixed-length packets, for example, packets in a voice network. This approach cannot be used in systems that use variable length packets, such as Internet Protocol data networks.
U.S. Pat. No. 5,291,481 (Doshi et al.) describes a congestion control method for high speed packet networks, which requires bandwidth reservation for individual voice calls. This approach requires a circuit-switched network, and is unsuitable for packet-switched networks that transmit integrated traffic.
U.S. Pat. No. 5,793,978 (Fowler) (commonly assigned with this patent application) describes a system for routing packets by separating packets into broadcast packets and non-broadcast packets and allocating a selected communication bandwidth to the broadcast packets. This approach is limited to the use of broadcast packets and non-broadcast packets. It is not intended for, or applicable to, integrated voice/data traffic.
U.S. Pat. No. 4,914,650 (Sriram) describes a bandwidth allocation and congestion control scheme. This approach uses multiple packet queues and applies a time slot scheme for selecting packets to be serviced.
The Diffserv Working Group of the Internet Engineering Task Force is developing standards and architectures for providing differentiated services in the Internet. For example, D. Clark et al., xe2x80x9cAn approach to service allocation in the Internet,xe2x80x9d Internet-draft, July 1997, describes a scheme of classifying packets into different service profiles, which are used to select packet drop preference policies at a network node. The dropping mechanism has a single queue with selective dropping.
K. Nichols et al., xe2x80x9cA two-bit differentiated service architecture for the Internet,xe2x80x9d Internet-draft, November 1997, combines the approach of Clark et al. with a proposal for a xe2x80x9cpremium service.xe2x80x9d The xe2x80x9cpremium servicexe2x80x9d proposal implements a guaranteed peak bandwidth service with negligible delay.
S. Blake et al., xe2x80x9cAn architecture for differentiated services,xe2x80x9d Internet-draft, August 1998, presents an architectural proposal for traffic profiles, and formally defines traffic conditioners.
The common drawback of Clark, Nichols, Blake, Sriram, and the other patents cited above, is that their approaches do not specifically exploit the redundant characteristics of voice and video signals and thus do not have an optimal drop policy for voice and video traffics. At the same packet drop rate, the quality of a voice or video transmission can vary greatly depending on how the packets within each stream are dropped. For example, dropping packets consecutively in large chunks or spreading drops out evenly will significantly affect quality. The prior solutions, one way or another, focus only on the contentions for bandwidth among multiple traffic classes.
Thus, there is a need for a mechanism that deals with both the contentions among traffic classes (using multiple queues) and the contentions among packets belonging to a same traffic class/stream (using sequence numbers). The end result is a better voice/video quality during periods of network congestion.
Based on the foregoing, it is desirable to provide a method for regulating packet traffic in a manner that minimizes loss of quality of the traffic.
In particular, there is a need for a fast, reliable, simple method of ensuring consistent quality of service for network transmissions of different types.
There is a need for such a method that guarantees high quality of service for real-time traffic, without starving data traffic of bandwidth.
The foregoing needs and objects, and other needs and objects that will become apparent from the following description, are achieved by the present invention, which comprises, in one aspect, a method of managing traffic directed from a first network element to a second network element in a packet-switched network, comprising the steps of receiving, from the first network element, a plurality of packets each including a drop priority value that indicates an order to drop the packet relative to other packets among the plurality of packets; storing the plurality of packets in a queue; detecting a drop condition, and in response thereto: selecting one or more packets of said plurality of packets based on said drop priority field, and dropping the selected packets from the queue while transmitting to the second network element all other packets of said plurality of packets.
According to one feature, the step of selecting includes selecting a first packet that is received after at least one other packet from said plurality of packets. In another feature, the step of receiving includes receiving a plurality of packets that includes a first subset of packets that each include a drop priority field set to a first drop value of a set of drop values and a second subset of packets that each include a drop priority field set to a second drop value of said set of drop values. A related feature is that the step of selecting includes selecting all packets from said first subset before selecting packets from said second subset.
In another related feature, the step of receiving a plurality of packets includes assigning the first drop values and the second drop values according to a pre-determined ratio. In yet another related feature, the step of receiving includes receiving a plurality of packets each having drop priority field values that form a sequence of consecutively greater integers.
Still another feature is that the step of selecting one or more packets comprises selecting only an earlier received packet that has a particular drop priority field value. According to yet another feature, the step of storing includes storing said plurality of packets in a first set of one or more first queues, and further comprising the step of storing a second plurality of packets in a second set of one or more second queues. Another feature is that the step of storing includes storing said plurality of packets either in a first set of one or more first queues, or in a second plurality of packets in a second set of one or more second queues, according to a type of traffic represented by the plurality of packets. A related feature is that the step of storing includes storing said plurality of packets in a queue selected from among a plurality of queues according to a type of data contained in each packet of said plurality of packets.
According to a further feature, the step of storing includes the step of storing said plurality of packets in a queue selected from among a plurality of queues according to a type of data contained in each packet of said plurality of packets; and storing packets containing voice traffic in a first queue of the plurality of queues and storing data traffic in a second queue of the plurality of queues.
The invention also encompasses many other aspects and features, as described in the following description and in the appended claims.